class H_BAG{E} < $BAG{E}

****	This Bag sorts its elements by counting the number of occurences. If two _different but equal_ elements are inserted only one of them will be stored, but this one will be yielded twice. _

---

Ancestors

$BAG{_}	$RO_BAG{_}	$STR	$CONTAINER{_}
$ELT{_}	$ELT

Descendants

BAG{_}

---

Public

Features

as_array: ARRAY{E} .. Included as as_array

copy: SAME

count(e:E): INT

****	Return the number of occurences of element "e"

count_if(test:ROUT{E}:BOOL):INT .. Included as count_if

****	The number of elements which satisfy `test'. Self may be void.

create(e: $ELT{E}): SAME

create: SAME

create_from(a: ARRAY{E}): SAME

****	Create a bag from the elements of array "a".

delete(e:E)

delete(e:E): E

delete_all(e:E)

****	Delete all elements equal to "e"

delete_all(e:E): INT

difference(a:$RO_BAG{E}): $BAG{E}

****	Returns a bag which represents the difference between self and "a"

elt_eq(e1,e2:ETP):BOOL .. Included as elt_eq

****	The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants.

elt_hash(e:ETP):INT .. Included as elt_hash

****	A hash value associated with an element. Must have the property that if "elt_eq(e1,e2)" then "elt_hash(e1)=elt_hash(e2)". Can be defined to always return 0, but many routines will then become quadratic. Uses object "id" by default. May be redefined in descendants.

elt_lt(e1,e2:ETP):BOOL .. Included as elt_lt

****	The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants.

elt_nil: ETP .. Included as elt_nil

****	Return the nil value. If the element is under $NIL then return e.nil. Otherwise, return void _

equals(a:$RO_BAG{E}): BOOL .. Included as equals

every(test:ROUT{E}:BOOL):BOOL .. Included as every

****	True if every element of self satisfies `test'. Self may be void.

has(e:E): BOOL

index_of(e: E):INT .. Included as index_of

****	Return index of leftmost element of self which is equal to "e" or -1 if there is none.

insert(e:E)

intersection(a:$RO_BAG{E}): $BAG{E}

****	The intersection of two bag has the element with the minimal occurence of both bags.

is_disjoint(a:$RO_BAG{E}): BOOL .. Included as is_disjoint

****	Returns 'true' if all elements of 'self' are not contained in 'a' and vice versa. Neither may be void.

is_elt_nil(e:ETP):BOOL .. Included as is_elt_nil

is_empty: BOOL .. Included as is_empty

****	Do not do size=0. Finding size may require iteration through all elements - quite wasteful for just "is_empty"

is_subset(a: $RO_BAG{E}): BOOL .. Included as is_subset

****	Returns true, if 'a' has all elements with higher occurences as self.

n_unique: INT

****	Return the number of unique indicies

notany(test:ROUT{E}:BOOL):BOOL .. Included as notany

****	True if none of the elements of self satisfies `test'. Self may be void.

notevery(test:ROUT{E}:BOOL):BOOL .. Included as notevery

****	True if not every element of self satisfies `test'. Self may be void.

size: INT .. Included as size

some(test:ROUT{E}:BOOL):BOOL .. Included as some

****	True if some element of self satisfies `test'. Self may be void.

str: STR .. Included as str

****	Prints out a string version of the array of the components that are under $STR

union(a: $RO_BAG{E}): SAME .. Included as union

****	Returns a set containing all elements being contained in the sets. The properties of the result are the ones from the first set. Neither of the sets may be void.

Iters

elt!: E

map_key!: K .. Included as unique!

---

Private

map_aget(k:K): E .. Included as aget

****	Returns the element equal to 'e' from the set. Returns void or T::nil if there is no such element. Self may not be void.

map_aset(k:K,e:E) .. Included as aset

****	Over-ride data if 'k' exists. Otherwise grow the bucket chain associated with hash(k)

attr asize: INT; .. Included as asize

****	The size of the fraction of the store which is currently in use. Array access beyond this bound is illegal.

attr asize: INT; .. Included as asize

****	The size of the fraction of the store which is currently in use. Array access beyond this bound is illegal.

attr bound: INT; .. Included as bound

****	Upper bound for split_pos. Is always initial_size * 2.pow(doubles)

attr bound: INT; .. Included as bound

****	Upper bound for split_pos. Is always initial_size * 2.pow(doubles)

bucket(i:INT): BUCKET .. Included as bucket

create_sized(initial_size:INT): SAME .. Included as create_sized

****	Creating a table with another minimal size. This might be useful to avoid shrinking of large table which might get very empty.

data_nil: E .. Included as data_nil

dbg: STR .. Included as dbg

****	Returns an interal string representation of the hashtable. For debugging only.

attr doubles: INT; .. Included as doubles

****	Number of times the initial table size has been doubled.

attr doubles: INT; .. Included as doubles

****	Number of times the initial table size has been doubled.

elt_eq(e1,e2:ETP):BOOL .. Included as elt_key_eq

****	The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants.

elt_hash(e:ETP):INT .. Included as elt_key_hash

****	A hash value associated with an element. Must have the property that if "elt_eq(e1,e2)" then "elt_hash(e1)=elt_hash(e2)". Can be defined to always return 0, but many routines will then become quadratic. Uses object "id" by default. May be redefined in descendants.

elt_nil: ETP .. Included as elt_key_nil

****	Return the nil value. If the element is under $NIL then return e.nil. Otherwise, return void _

elt_str(e: E): STR .. Included as elt_str

****	Return a string representing the element "e"

grow .. Included as grow

****	Increases the size of the array by one. The functions changing the size of the bucket table: They are split into two parts. 1.) Splitting the next bucket into two. (update_*) 2.) Resizing the storage area. (shrink/grow)

hash(e:E): INT .. Included as hash

****	Returns the bucket to store e. This number will be generated from the hash-value and be normailzed through the actual size of the set.

internal_create: SAME

****	Redefine the stub routine in "BAG_INCL"

shared lower_fill_ratio: FLT := 0.800; .. Included as lower_fill_ratio

shared lower_fill_ratio: FLT := 0.800; .. Included as lower_fill_ratio

map_copy: SAME .. Included as map_copy

****	Returns a copy of self with all properties set like self.

map_delete(k:K): E .. Included as map_delete

****	Removes an element from the set. Does nothing if there is no such element.

map_elt!: E .. Included as map_elt!

map_has_ind(k:K): BOOL .. Included as map_has_ind

map_pair!: TUP{K,E} .. Included as map_pair!

attr minsize: INT; .. Included as minsize

****	Lower bound for the store size.

attr minsize: INT; .. Included as minsize

****	Lower bound for the store size.

attr n_inds: INT; .. Included as n_inds

****	Returns the number of elements (resp. indices) in the table.

attr n_inds: INT; .. Included as n_inds

****	Returns the number of elements (resp. indices) in the table.

create: SAME .. Included as old_create

set_bucket(i:INT,l:BUCKET) .. Included as set_bucket

shrink .. Included as shrink

****	Decreases the size of the array by one. Resizes the storage area, if neccessary.

attr split_pos: INT; .. Included as split_pos

****	Position of the next bucket to split.

attr split_pos: INT; .. Included as split_pos

****	Position of the next bucket to split.

attr store: AREF{BUCKET}; .. Included as store

****	Here is the data being stored.

attr store: AREF{BUCKET}; .. Included as store

****	Here is the data being stored.

attr total_size: INT;

attr total_size: INT;

update_delete .. Included as update_delete

****	Checks the actual fill ratio of the set. Removes a bucket from the hash table if the ratio is low enough.

update_insert .. Included as update_insert

****	Checks the actual fill ratio of the set. Adds a bucket to the hash table if the ratio is high enough. The functions changing the size of the bucket table are split into two parts. 1.) Splitting the next bucket into two. (update_*) 2.) Resizing the storage area. (shrink/grow)

shared upper_fill_ratio: FLT := 1.000; .. Included as upper_fill_ratio

****	For fast access one needs a low ratio between number of elements in the and number of cells. For efficient memory usage one needs a high ratio. The ratio should always be between these two bounds (unless the table is really small; where the ratio can get even lower.)

shared upper_fill_ratio: FLT := 1.000; .. Included as upper_fill_ratio

****	For fast access one needs a low ratio between number of elements in the and number of cells. For efficient memory usage one needs a high ratio. The ratio should always be between these two bounds (unless the table is really small; where the ratio can get even lower.)

---

The Sather Home Page

---